package leetcode.code090;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution1 extends Solution090 {

	@Override
	public List<List<Integer>> subsetsWithDup(int[] nums) {
		Arrays.sort(nums);
		List<Integer> temp = new ArrayList<>();
		List<List<Integer>> ans = new ArrayList<>();
		this.subsetsWithDup(false, 0, nums, temp, ans);
		return ans;
	}

	public void subsetsWithDup(boolean choosePre, int cur, int[] nums, List<Integer> temp, List<List<Integer>> ans) {
		if (cur == nums.length) {
			ans.add(new ArrayList<>(temp));
			return;
		}
		subsetsWithDup(false, cur + 1, nums, temp, ans);
		if (cur > 0 && nums[cur] == nums[cur - 1] && !choosePre) {
			return;
		}
		temp.add(nums[cur]);
		subsetsWithDup(true, cur + 1, nums, temp, ans);
		temp.remove(temp.size() - 1);
	}

	public static void main(String[] args) {
		Solution1 so = new Solution1();
//		so.debug1();
//		so.debug2();
		so.debug3();
		so.debug4();
	}

}
